/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***动态规划算法         P158                   ***/
/***C++ 实现版本    written by Daniel           ***/

#include <iostream>
#include <memory>
#include <map>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::map;

class DynamicPro
{
public:
    DynamicPro(map<int,int> vWMap, int bagCap):weightValue(vWMap),bagCapacity(bagCap)
    {
        weightValue.insert(std::make_pair(0,0));
    }
    int max(int a, int b)
    {
        return a>=b?a:b;
    }
    int getMaxValue()
    {
        int count=weightValue.size();
        vector<vector<int>> dyVec(count,vector<int>(bagCapacity+1,0));
        int i=0,j=0;
        for(const auto &item:weightValue){
            for(j=0;j<=bagCapacity;j++){
                if (i==0 || j==0){
                    dyVec[i][j]=0;
                    continue;
                }
                //背包容量小于当前物品重量
                if (j<item.first){
                    dyVec[i][j]=dyVec[i-1][j];
                }
                else{
                    dyVec[i][j]=max(dyVec[i-1][j],item.second+dyVec[i-1][j-item.first]);
                }
            }
            i++;
        }
        maxValue=dyVec[i-1][j-1];
        return dyVec[i-1][j-1];
    }
private:
    //质量和价值的对应表
    map<int, int> weightValue;
    //最大价值
    int maxValue;
    //背包容量
    int bagCapacity;
};

int main()
{
    map<int, int> valueTable;
    vector<std::pair<int,int>> vec(1,std::pair<int,int>(1,1));
    valueTable.insert(std::make_pair(1,1500));
    valueTable.insert(std::make_pair(4,3000));
    valueTable.insert(std::make_pair(3,2000));
    valueTable.insert(std::make_pair(2,2000));
    valueTable.insert(std::make_pair(5,10000));
    // valueTable.insert(std::make_pair(2,2000));
    DynamicPro dy(valueTable,6);
    cout<<dy.getMaxValue()<<endl;
}